package com.formula.datastructure.exercise.graph.undirect.mst;
// 仅参考, 其实书上讲得更好, https://www.cnblogs.com/zyker/p/5934922.html

import com.formula.datastructure.exercise.graph.undirect.ListEdge;
import com.formula.datastructure.exercise.graph.undirect.ListGraph;
import com.formula.datastructure.exercise.graph.undirect.ListVertex;

/**
 * 最小生成树只有无向图
 * Kruskal更适合稀疏图, 算法要注意三点:
 * #1 要有所有边的数组, 知道一条边的from和to
 * #2 时间复杂度和sort算法有关, 只用sort一次
 * #3 用并查集
 */
public class Kruskal {

    private int[] root;

    /**
     * 思想: 最小生成树有n个顶点, n-1条边
     * 一来就把n个顶点加入, 不加入任何边
     * 然后找n-1次, 每次添加一条边, 添加的边需要满足两点:
     * #1, 不产生回路
     * #2, 且权值最小
     * <p>
     * 算法需要排序, 所以排序也影响复杂度
     * 如何判断是否产生回路: 用并查集
     */
    public ListEdge[] getMST(ListGraph graph) {

        // 初始化count和结果集
        int N = graph.vertexSize();
        int count = 0;
        ListEdge[] result = new ListEdge[N - 1];
        // 初始化并查集, 每个点的root就是自己
        root = new int[N];
        for (int i = 0; i < N; i++) {
            root[i] = i;
        }

        ListEdge[] allEdges = graph.egdgList;
        allEdges = sort(allEdges, graph.edgeSize());
        for (int i = 0; i < allEdges.length; i++) {
            int fromRoot = getRoot(allEdges[i].fromIdx);
            int toRoot = getRoot(allEdges[i].toIdx);
            // 通过并查集发现没有回路
            if (fromRoot != toRoot) {
                result[count++] = allEdges[i];
                // merge谁为祖先都可以, 就是要保证一致性, 要么全部是to的root, 要不全部是from的root
                // 把to的root设置为from的root
                root[toRoot] = fromRoot;
                System.out.println("From: " + graph.vertexList[allEdges[i].fromIdx].data + ", To :" + graph.vertexList[allEdges[i].toIdx].data + ", weight : " + allEdges[i].weight);
                if (count == N - 1) {
                    break;
                }
            }
        }

        return result;
    }

    private int getRoot(int idx) {
        // 如果是自己就到头了, 如果不是自己就继续找父亲的父亲, 也就是根
        while (idx != root[idx]) {
            idx = root[idx];
        }
        return idx;
    }

    private ListEdge[] sort(ListEdge[] edges, int size) {

        for (int i = 1; i < size; i++) {
            ListEdge insert = edges[i];
            int idx = i;
            for (int j = i - 1; j >= 0; j--) {
                if (edges[i].weight < edges[j].weight) {
                    edges[j + 1] = edges[j];
                    idx = j;
                }
            }
            if (idx != i) {
                edges[idx] = insert;
            }
        }
        return edges;
    }

    public static void main(String[] args) {
        testListGraph();
    }

    private static void testListGraph() {
        ListGraph graph = new ListGraph();
        ListVertex A = new ListVertex("A");
        ListVertex B = new ListVertex("B");
        ListVertex C = new ListVertex("C");
        ListVertex D = new ListVertex("D");
        ListVertex E = new ListVertex("E");
        ListVertex F = new ListVertex("F");

        ListEdge edge1 = new ListEdge(0, 1, 5);
        ListEdge edge2 = new ListEdge(0, 3, 9);
        A.addEdge(edge1);
        A.addEdge(edge2);

        ListEdge edge3 = new ListEdge(1, 2, 2);
        ListEdge edge4 = new ListEdge(1, 3, 10);
        B.addEdge(edge3);
        B.addEdge(edge4);

        ListEdge edge5 = new ListEdge(2, 4, 8);
        ListEdge edge6 = new ListEdge(2, 5, 7);
        C.addEdge(edge5);
        C.addEdge(edge6);

        ListEdge edge7 = new ListEdge(3, 4, 4);
        D.addEdge(edge7);


        ListEdge edge8 = new ListEdge(5, 5, 7);
        E.addEdge(edge8);

        ListEdge edge9 = new ListEdge(6, 1, 6);
        F.addEdge(edge9);

        graph.insertVex(A);
        graph.insertVex(B);
        graph.insertVex(C);
        graph.insertVex(D);
        graph.insertVex(E);
        graph.insertVex(F);

        Kruskal kruskal = new Kruskal();
        kruskal.getMST(graph);
    }
}
